#!/usr/bin/python3.5

# -*- coding: utf-8 -*-



def _quick(arr,l,r):

    base = arr[l]
    cur = l+1
    pre = l
    while cur<r:
        if arr[cur] < base:
            pre+=1
            arr[cur],arr[pre] = arr[pre],arr[cur]
        cur+=1
    arr[l],arr[pre] = arr[pre],arr[l]
    return pre

def QuickSort(arr,l,r):
    if l>=r:
        return
    mid = _quick(arr,l,r)
    print(mid)
    QuickSort(arr,l,mid)
    QuickSort(arr, mid+1, r)
    return arr



# def quck(arr, l, r):
#    base = arr[l]
#    cur = l + 1
#    pre = l
#    while cur < r:
#        if arr[cur] > base:
#            cur += 1
#        else:
#            pre += 1
#            arr[pre], arr[cur] = arr[cur], arr[pre]
#            cur += 1
#    arr[l], arr[pre] = arr[pre], arr[l]
#    return pre
#
#
# def QuickSort(arr, l, r):
#     if l >= r:
#         return
#     mid = quck(arr, l, r)
#     # print(mid,arr[l:mid],arr[mid+1:r])
#     QuickSort(arr, l, mid)
#     QuickSort(arr, mid + 1, r)
#     return arr


if __name__ =="__main__":

    a = [2, 8, 4, 5, 9, 4, 42, 0, 3, 6, 8]
    print(QuickSort(a,0,11))
